// Import any package as required


import java.io.*;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Set;

public class HuffmanSubmit implements Huffman {

    // Feel free to add more methods and variables as required.

    public void encode(String inputFile, String outputFile, String freqFile) {
        // TODO: Your code here
        BinaryIn binaryIn = new BinaryIn(inputFile);
        // freq
        int[] arrays = new int[256];
        int ascii = 0;
        while (!(binaryIn.isEmpty())) {
            ascii = binaryIn.readChar();
            arrays[ascii]++;
        }
        //freqFile
        BinaryOut freq = new BinaryOut(freqFile);
        for (int i = 0; i < arrays.length; i++) {
            freq.write(Integer.toBinaryString(i) + ":" + arrays[i] + "\n");
        }
        freq.flush();
        freq.close();


        //freq to huffman tree
        LinkedList<Node<String>> list = createNodeList(arrays);
        Node<String> root = CreateHFMTree(list);
        inOrder(root);
        HashMap<String, String> map = getAllCode(root);

        //get huffman code
        binaryIn = new BinaryIn(inputFile);
        String str = "";
        while (!(binaryIn.isEmpty())) {
            ascii = binaryIn.readChar();
            str += map.get((char) ascii + "");
        }

        BinaryOut binaryOut = new BinaryOut(outputFile);
        compressFile(binaryOut, str);
        binaryOut.flush();
        binaryOut.close();
    }


    @Override
    public void decode(String inputFile, String outputFile, String freqFile) throws IOException {
        // TODO: Your code here
        BinaryIn binaryIn = new BinaryIn(inputFile);
        BinaryOut fileUncompress = new BinaryOut(outputFile);
        uncompressFile(freqFile, binaryIn, fileUncompress);//解压文件至fileUncompress处
    }


    public static void main(String[] args) throws IOException {
        Huffman huffman = new HuffmanSubmit();
//        huffman.encode("test.txt", "test.enc", "freq.txt");
//        huffman.decode("test.enc", "test_dec.txt", "freq.txt");
//        huffman.encode("alice30.txt", "alice30.enc", "freq.txt");
//        huffman.decode("alice30.enc", "alice30_dec.txt", "freq.txt");
        huffman.encode("ur.jpg", "ur.enc", "freq.txt");
        huffman.decode("ur.enc", "ur_dec.jpg", "freq.txt");
        // After decoding, both ur.jpg and ur_dec.jpg should be the same.
        // On linux and mac, you can use `diff' command to check if they are the same.
    }


    public class Node<T> implements Comparable<Node<T>> {
        private T data;
        private int weight;
        private Node<T> left;
        private Node<T> right;

        public Node(T data, int weight) {
            this.data = data;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "data:" + data + "   " + "weight:" + weight;
        }


        @Override
        public int compareTo(Node<T> o) {
            if (this.weight > o.weight) {
                return 1;
            } else if (this.weight < o.weight) {
                return -1;
            }
            return 0;
        }

        public void setData(T data) {
            this.data = data;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }

        public T getData() {
            return data;
        }

        public int getWeight() {
            return weight;
        }

        public void setLeft(Node<T> node) {
            this.left = node;
        }

        public void setRight(Node<T> node) {
            this.right = node;
        }

        public Node<T> getLeft() {
            return this.left;
        }

        public Node<T> getRight() {
            return this.right;
        }
    }

    /**
     * 把获得的数组转化为节点并存在链表中
     *
     * @param arrays
     * @return
     */
    public LinkedList<Node<String>> createNodeList(int[] arrays) {
        LinkedList<Node<String>> list = new LinkedList<>();
        for (int i = 0; i < arrays.length; i++) {
            if (arrays[i] != 0) {
                String ch = (char) i + "";
                Node<String> node = new Node<String>(ch, arrays[i]); //构建节点并传入字符和权值
                list.add(node); //添加节点
            }
        }
        return list;
    }


    public Node<String> CreateHFMTree(LinkedList<Node<String>> list) {
        while (list.size() > 1) {
            sortList(list); //排序节点链表
            Node<String> nodeLeft = list.removeFirst();
            Node<String> nodeRight = list.removeFirst();
            Node<String> nodeParent = new Node<String>(null, nodeLeft.getWeight() + nodeRight.getWeight());
            nodeParent.setLeft(nodeLeft);
            nodeParent.setRight(nodeRight);
            list.addFirst(nodeParent);
        }
        //System.out.println("根节点的权重：" + list.get(0).getWeight());
        return list.get(0);//返回根节点
    }

    public void sortList(LinkedList<Node<String>> list) {
        for (int i = list.size(); i > 1; i--) {
            for (int j = 0; j < i - 1; j++) {
                Node<String> node1 = list.get(j);
                Node<String> node2 = list.get(j + 1);
                if (node1.getWeight() > node2.getWeight()) {
                    int temp;
                    temp = node2.getWeight();
                    node2.setWeight(node1.getWeight());
                    node1.setWeight(temp);
                    String tempChar;
                    tempChar = node2.getData();
                    node2.setData(node1.getData());
                    node1.setData(tempChar);
                    Node<String> tempNode = new Node<String>(null, 0);
                    tempNode.setLeft(node2.getLeft());
                    tempNode.setRight(node2.getRight());
                    node2.setLeft(node1.getLeft());
                    node2.setRight(node1.getRight());
                    node1.setLeft(tempNode.getLeft());
                    node1.setRight(tempNode.getRight());
                }
            }
        }
    }

    public void inOrder(Node<String> root) {
        if (root != null) {
            inOrder(root.getLeft());
            if (root.getData() != null) {
                //System.out.println(root.getData());
            }
            inOrder(root.getRight());
        }
    }

    public void inOrderGetCode(String code, HashMap<String, String> map, Node<String> root) {
        if (root != null) {
            inOrderGetCode(code + "0", map, root.getLeft());
            if (root.getLeft() == null && root.getRight() == null)//存储叶子结点的哈夫曼编码
            {
                //System.out.println(root.getData());
                //System.out.println(code);
                map.put(root.getData(), code);
            }
            inOrderGetCode(code + "1", map, root.getRight());
        }
    }

    public HashMap<String, String> getAllCode(Node<String> root) {
        HashMap<String, String> map = new HashMap<>();
        inOrderGetCode("", map, root);
        return map;
    }


    public void compressFile(BinaryOut fileCompress, String HFMcode) {
        //writeHashMap(map, fileCompress);  //写HashMap的数据
        writeHFMcode(HFMcode, fileCompress); //继续写HFMcode 01字符串
    }


    public void writeHashMap(HashMap<String, String> map, BinaryOut file) {
        int size = map.size(); //获取编码的个数，即HashMap中的键值对个数
        String temp = ""; //存放临时8位01字符串
        int value = 0; //存放01字符串转化得到的ASCII值
        file.write(size);  //写HashMap长度
        Set<String> keySet = map.keySet(); //获取HashMap存放key的容器
        java.util.Iterator<String> it = keySet.iterator();//通过容器获取迭代器
        while (it.hasNext()) //迭代判断，有下一个key
        {
            String key = it.next(); //取出下一个key
            String code = map.get(key); //取出code
            file.write(key.charAt(0)); //写key值
            int a = code.length() / 8;//能存满的字节数
            int b = code.length() % 8;//剩余的位数
            int c = 1; //值对应的存储的字节数
            if (b == 0) //无剩余位
            {
                c = a;
                file.write(c);  //写code的字节数
                file.write(0);  //写补0数，为0个
                for (int i = 0; i < a; i++) //写code值
                {
                    temp = "";
                    for (int j = 0; j < 8; j++) {
                        temp += code.charAt(i * 8 + j);
                    }
                    value = StringToInt(temp);
                    file.write(value); //逐一把code的每一位写出去
                }
            } else {
                c = a + 1;
                file.write(c); //写code的字节数
                file.write(8 - b); //写补0数
                for (int i = 0; i < 8 - b; i++) //补0
                {
                    code += "0";
                }
                for (int i = 0; i < c; i++) {
                    temp = "";
                    for (int j = 0; j < 8; j++) {
                        temp += code.charAt(8 * i + j);
                    }
                    value = StringToInt(temp);
                    file.write(value); //逐一写code，包括补的0
                }
            }
        }
    }

    public int StringToInt(String temp) {
        int value = 0;
        for (int i = 0; i < 8; i++) {
            int x = temp.charAt(i) - 48;
            if (x == 1)    //为1则累加入value
            {
                value += Math.pow(2, 7 - i);  //表示2的(7-i)次方
            }
        }
        return value;
    }


    public void writeHFMcode(String HFMcode, BinaryOut file) {
        int len = HFMcode.length();  //获取HFMcode长度
        int b = len % 8;   //求出剩余的位数
        int c = b == 0 ? 0 : 8 - b; //计算补0数
        file.write(c); //写补0数
        for (char cc : HFMcode.toCharArray()) {
            file.write(cc == '0' ? false : true);
        }

    }

    public void uncompressFile(String freq, BinaryIn fileCompress, BinaryOut fileUncompress) throws IOException {
        //HashMap<String, String> mapGet = readHashMap(fileCompress); //获取哈希表
        HashMap<String, String> mapGet = getMapFromFreqFile(freq);
        String str = readHFMStr(fileCompress);  //获取01字符串
        writeFile(str, mapGet, fileUncompress);  //写文件到保存路径
    }


    public HashMap<String, String> readHashMap(BinaryIn fileCompress) {
        HashMap<String, String> mapGet = new HashMap<>();
        int keyNumber = fileCompress.readInt(); //读取key的数量
        String key = ""; //HashMap的键值对
        String code = ""; //未去0的字符串
        String codeRZ = "";//去0的字符串
        int length = 0; //表示还原后的字符串的理论长度，解决字符串前面的0的问题
        int byteNum = 1; //当前code占了几个字节
        int addZero = 0; //补0数
        int value = 0; //临时储值
        int zeroLength = 0;//code没有1的时候的字符串长度
        for (int i = 0; i < keyNumber; i++) {
            key = (char) fileCompress.readInt() + ""; //获取key值
            byteNum = fileCompress.readInt(); //获取code的字节数
            addZero = fileCompress.readInt(); //读取补0数量
            if (addZero == 0) //没有补0，是整字节数
            {
                for (int k = byteNum - 1; k >= 0; k--) {
                    value += fileCompress.readInt() * (Math.pow(2, k * 8));
                }
                code = IntToString(value);//把数值转为01code
                value = 0;//清零
                length = 8 * byteNum - code.length();//计算在前面要补多少0
                if (code.length() == 0)  //若code内数字都为0，只要去掉尾部即可
                {
                    zeroLength = length - addZero;  //计算有多少个0
                    for (int k = 0; k < zeroLength; k++) {
                        codeRZ += "0";
                    }
                } else    //code值不为0，补充前面的0，去掉后面的0
                {
                    for (int k = 0; k < length; k++) {
                        codeRZ += "0";
                    }
                    for (int k = 0; k < code.length() - addZero; k++) {
                        codeRZ += code.charAt(k);
                    }
                }
            } else  //有补0
            {
                for (int k = byteNum - 1; k >= 0; k--) {
                    value += fileCompress.readInt() * (Math.pow(2, k * 8));
                }
                code = IntToString(value);//把数值转为01code
                value = 0;//清0
                length = 8 * byteNum - code.length();//计算在前面要补多少0
                if (code.length() == 0)  //若code内数字都为0，只要去掉尾部即可
                {
                    zeroLength = length - addZero;  //计算有多少个0
                    for (int k = 0; k < zeroLength; k++) {
                        codeRZ += "0";
                    }
                } else   //code值不为0，补充前面的0，去掉后面的0
                {
                    for (int k = 0; k < length; k++) {
                        codeRZ += "0";
                    }
                    for (int k = 0; k < code.length() - addZero; k++) //不要后面的0
                    {
                        codeRZ += code.charAt(k);
                    }
                }
            }
            mapGet.put(key, codeRZ); //把读取到的键值对存入创建的HashMap
            codeRZ = ""; //清空
        }
        return mapGet;
    }

    public String IntToString(int value) {
        String temp1 = ""; //存放反的字符串
        String temp = "";  //存放正的字符串
        while (value > 0) //逐渐取出各个二进制位数，字符串为反向的
        {
            temp1 += value % 2;
            value = value / 2;
        }
        for (int i = temp1.length() - 1; i >= 0; i--) {
            temp += temp1.charAt(i);
        }
        return temp;
    }

    public String readHFMStr(BinaryIn fileCompress) {
        String str1 = ""; //存放获取到的直接的01字符串
        String str = ""; //存放去掉补0的字符串
        int value = 0;
        String temp = "";
        int addZero = fileCompress.readInt(); //读取整个文件的补0个数
        while (!fileCompress.isEmpty()) {
            value = fileCompress.readChar();
            temp = IntToStringEight(value); //把每个字节的数据转化为八位的01
            str1 += temp;
        }
        if (addZero != 0) //有补0，获取补0前的字符串
        {
            str = str1.substring(0,str1.length() - addZero);
            return str;
        }
        return str1;
    }


    public String IntToStringEight(int value) {
        String temp1 = ""; //存放反的字符串
        String temp = "";  //存放正的字符串
        int add = 0;
        while (value > 0) //逐渐取出各个二进制位数，字符串为反向的
        {
            add++;
            temp1 += value % 2;
            value = value / 2;
        }
        add = 8 - add;
        for (int i = 0; i < add; i++)//添0至8位
        {
            temp1 += "0";
        }
        for (int i = temp1.length() - 1; i >= 0; i--) //反向的字符串获取正向的字符串
        {
            temp += temp1.charAt(i);
        }
        return temp;
    }


    public void writeFile(String str, HashMap<String, String> mapGet, BinaryOut fileCompress) {
        int len = str.length();//获取01串的长度
        String temp = ""; //临时存放段的01字符串
        for (int i = 0; i < len; i++) {
            temp += str.charAt(i);
            if (mapGet.containsKey(temp)) {
                char c = mapGet.get(temp).charAt(0);
                fileCompress.write(c); //一个字符的字符串转字符然后写出
                temp = "";
            }
        }
        fileCompress.close();
    }


    public HashMap<String, String> getMapFromFreqFile(String freqFile) throws IOException {
        int[] arrays = new int[256];
        InputStream in = new FileInputStream(freqFile);//
        BufferedReader in2 = new BufferedReader(new InputStreamReader(in));
        String y = "";
        while ((y = in2.readLine()) != null) {//一行一行读
            int i = Integer.parseInt(y.split(":")[0], 2);
            int freq = Integer.valueOf(y.split(":")[1]);
            arrays[i] = freq;
        }
//        System.out.println(arrays);
        LinkedList<Node<String>> list = createNodeList(arrays);
        Node<String> root = CreateHFMTree(list);
        inOrder(root);
        HashMap<String, String> temp = getAllCode(root);
        HashMap<String, String> res = new HashMap<>();
        for (String key : temp.keySet()) {
            String value = temp.get(key).toString();
            res.put(value, key);
        }
        return res;
    }
}